The field of mobile mesh networks, often referred to interchangeably with Mobile Adhoc Networks (MANETs) is attracting increasing interest as a field of research because of their suitability to a variety of military and commercial applications. Specifically, mesh networks are important in settings where telecommunication facilities must be installed quickly, as in disaster recovery or in combat, and in areas where a large coverage footprint is desirable.
Conventional wireless (e.g., 802.11, 802.16) and cellular networks are infrastructure-based networks which utilize a hub-and-spoke model (point-to-multipoint topology). In the hub-and-spoke model, all wireless devices must be within broadcast range of a central access point (AP) to communicate. All data traffic must pass through this point as no two host devices communicate directly. In addition, mobility is supported only by a subset of the nodes (end host devices), while infrastructure nodes are often still assumed to be fixed.
For example, FIG. 1 depicts a hub-and-spoke model (102) which may be used by conventional wireless networks using 802.11 and/or 802.16. In an 802.11 environment, an access point (104) may communicate directly with a client station 106. In terms of network formation, to enter a Basic Service Set (BSS), client stations (STA) such as client station (106) must obtain synchronization information from access point (104). This may be done through one of two methods: (1) Passive scanning—where a client station waits to hear a beacon packet which is sent periodically from the access point containing the synchronization information, or (2) Active scanning—where the client station tries to find an access point by transmitting probe requests and waiting for probe responses from the access point. Either method may be chosen according to power consumption/performance trade-offs. An authentication exchange may follow so a client station (106) may prove its knowledge of a password. Finally, the association process may allow client station (106) and access point (104) to become aware of each-other's capabilities. Not until this process is complete is the client station (106) capable of transmitting and receiving data frames.
For coordination of medium access, the 802.11 standard relies on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) with a random backoff mechanism. Namely, when a node receives a packet that is to be sent, it checks to be sure the channel is clear (no other node is transmitting at the time). If the channel is clear, then the packet is sent. If the channel is not clear, the node waits for a randomly chosen period of time, and then checks again to see if the channel is clear. This period of time is called the backoff factor, and is counted down by a backoff counter. If the channel is clear when the backoff counter reaches zero, the node re-transmits the packet. If the channel is not clear when the backoff counter reaches zero, the backoff factor is set again, and the process is repeated. Because the probability that two nodes will choose the same back off factor is small, collisions between packets are minimized. However, transmission of a streamy burst of traffic by one node may result in temporarily monopolizing the medium at the cost of all other nodes being held off.
Although conventional wireless networking standards such as 802.11 claim to provide a mesh capability through Independent Basic Service Sets (IBSS), this requires that all nodes be directly connected by virtue of being within omni-directional antenna range from each other, because traffic cannot be forwarded, thus restricting network topology. The 802.11s proposal is aimed at true mesh networks where nodes now route information. However the 802.11s proposal does not discuss nor tackle mesh networks that use highly directional antennas. The use of highly directional antennas improves reach of the network over networks using omni-directional antennas. However, with the narrower beam of highly directional antennas, each node may theoretically communicate with only one other node at a time. The nodes must point their respective antenna toward each other. Thus, nodes must assume a schedule in which communications to their neighbors are organized in a way that maximizes medium sharing but still reduces interference. Specifically, each node in a set of nodes may communicate simultaneously with another node in a mutually exclusive set of nodes. The mechanism for accessing the medium is referred to as Time Division Pairwise Access (TDPA). Issues of scheduling brought on by directivity are described as “the antenna problem” or the “directivity scheduling problem.”
In the 802.11s proposal, medium access is strictly contention-based through use of virtual carrier sensing. Contention-based medium access approaches utilize bandwidth and reserved frequency channels merely for sensing the medium and by requiring the reservation of the medium each time a node wants to communicate—bandwidth and frequencies that could otherwise be used for transporting user data. Furthermore, the risk of monopolizing the medium remains when a node that is granted the medium is the source of a large burst of traffic.
The 802.16 standard is another infrastructure-based network that implements at least one Subscriber Station (SS) communicating with a Base Station (BS) via a point-to-multipoint air interface. For example, FIG. 1 depicts a hub-and-spoke model (102) which may be used by a conventional wireless 802.16 network. In FIG. 1, subscriber stations (110, 112, 114, and 116) communicate with a Base Station (BS) (108) via a point-to-multipoint air interface.
The downlink (i.e., the link from the base station (108) to the client stations) operates on a point-to-multipoint basis. In this sense, the medium is truly shared, much as it is in a wired LAN such as Ethernet. Using sectorized antennas, within a given frequency channel and antenna sector, all stations receive the same transmission. The base station (108) is the only transmitter operating in this direction, so it transmits without having to coordinate with other stations, except for the overall time division duplexing that may divide time into uplink and downlink transmission periods. Depending on the class of service provided, subscriber stations (110-116) may be issued continuing rights to transmit or the right to transmit may be granted by the BS (108) after receipt of a request from the user.
In the 802.16 world, WiMax mesh extensions seem to only address fixed mesh networks with the option to have centralized or distributed slot allocation for TDMA-based scheduling. In the former, slot allocation is determined at a single node known as the “Mesh Base Station”—an infrastructure-based approach, while the latter approach requires the distribution of schedules to all neighbors since nodes “compete” for available slots and must find out when “their bid” is unsuccessful.
In directional mobile mesh (Ad-hoc) networks, highly directional antennas are used giving the network longer reach than networks using omni-directional antennas. Each node must “take a turn” to communicate with each of its neighbors, but a set of nodes can communicate simultaneously with a mutually exclusive set of nodes.
A legacy approach to network formation involves use of a lengthy and complex approach for network formation. In the legacy approach, semi-centralized control, and frequent operator intervention were required. Specifically, a single unit was designated as the Network Control Unit (NCU) and this unit was commanded to initiate the network formation process. The NCU conducted a discovery scan by assuming the role of “interrogator” while all other nodes would be placed in the “responder” role. This implied that initially, the NCU conducted a discovery scan by transmitting a sequence of messages initiating what could become multiple instances of a link establishment handshake.
In this 360-degree “Alert” scan, covering n distinct bearings, the interrogator would transmit an “Alert” message in each direction, and all responders would be “listening” (receiving) in the opposite (reciprocal) direction. This way, whether the scan consisted of sequential or a predetermined order of bearings to be visited, there was a 1/n probability that if the interrogator and a responder were within communications range of each other, at some point during the scan, they would “face each other” and the responder would “hear” the interrogator.
The network expanded in this fashion, thus building up the connectivity in phases, where nodes formed concentric rings or levels, each said level executing a different phase of the process. Once no nodes were found by the nodes at the last level, and the nodes at every level estimated every other node had learned of the identity of every node and of the network's connectivity (a process referred to as reaching network closure), every node would compute a global schedule (a schedule for every node) that was a function of the network topology and specific time-late and throughput requirements.
This was based on the premise that because every node had the same input knowledge, by applying the same algorithm, every node computed the same schedule. Furthermore, this process required that nodes transition to using the local portion of this schedule (i.e., the portion of the schedule pertaining to that node and its neighbors) simultaneously and doing so would also incur large delays that were a function of the worst case network topology. All this time, nodes were not permitted to exchange user data. The only exchanges constituted link establishment protocols and network management knowledge propagation.
Once nodes were participating in steady-state communications via this TDPA schedule (i.e., nodes had transitioned to the operational state of the node and were finally permitted to exchange user data), and as nodes would move within or beyond communications range of others, links would form and/or drop. In addition, a set of acquisition functions were required in order to bring additional nodes into the network, or to re-acquire recently lost links. Most of these functions required operator intervention and the resulting changes in connectivity would imply the need for recalculation of the global schedule, which in turn implied another lengthy delay as knowledge about these changes again had to be propagated to every node in the network prior to the recalculation of a new schedule and eventual transition to it.
The activities taking place in this lengthy process are illustrated in FIG. 2. Image (202) of FIG. 2 shows a central node (204) searching for peers as an interrogator. Links are established with each discovered node as shown in image (206). Responding nodes as illustrated in image (208) become interrogators. Previously established links are maintained on a temporary maintenance schedule. The next levels of links are then established as shown in image (210). In image (212), a new level of interrogators may begin searching for peers. A network forms in concentric rings or levels using temporary schedules until no other peer can be found at the last level encountered. As nodes learn about each other and determine that unconnected peers are within range, cross links are established as shown in image (214). Information from every node (identity, position, connectivity, etc.) is propagated until every node determines that it knows about every other node. As shown in image (216) every network node calculates an identical global TDPA schedule and synchronizes its transition to the local portion of that schedule. Once nodes begin using their newly computed schedule, lost and newly acquired links trigger a lengthy network-wide propagation of the event and the recalculation of any transition to a new schedule as shown in image (218).
This complex and long process must take place merely for the purpose of forming the network and establishing a schedule, at which time, nodes are finally permitted to begin exchanging user data. Furthermore, any later changes in network connectivity or link attributes require yet again, the lengthy network-wide propagation of these changes and subsequent recalculation of, and transition to, a new global schedule.
Thus, it would be advancement in the art to provide mechanisms for self-forming, self-maintaining a directional mobile mesh network, where medium access coordination and adaptation is such that it impacts a minimal number of nodes.